/**
 * @Author: Liu, Yunfeng
 * @DateTime: 2021/3/2 20:02
 * @Description: 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 */
public class maxSubArray {
    public static int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = 0;
        int preSum = 0;
        for (int i : nums) {
            currentSum = Math.max(i, preSum + i);
            maxSum = Math.max(maxSum, currentSum);
            preSum = currentSum;
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums));
    }
}
/*
 *Dp[i] = max(Dp[i],i)
 * 加入下一个后比较是从上一个开始和比较大还是从上一个最大值开始处和比较大
 */
